#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年03月15日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''


class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @return: Find all unique triplets in the array which gives the sum of zero.
    """
    def threeSum(self, numbers):
        # write your code here
        length = len(numbers)
        numbers = sorted(numbers)
        res = list()

        for i in range(length):
            start = i + 1
            end = length - 1
            if i > 0 and numbers[i] == numbers[i-1]:
                continue

            while start < end:
                if start > i + 1 and numbers[start] == numbers[start-1]:
                    start += 1
                    continue
                
                if numbers[start] + numbers[end] > -numbers[i]:
                    end -= 1
                elif numbers[start] + numbers[end] < -numbers[i]:
                    start += 1
                else:
                    tmp = list()
                    tmp.append(numbers[i])
                    tmp.append(numbers[start])
                    tmp.append(numbers[end])
                    res.append(tmp)
                    start += 1
                    end -= 1
        return res